package com.framework.collection.List;

import lombok.val;

import javax.swing.plaf.IconUIResource;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * @author duanzhizhou
 * @date 2025/4/21
 */
public class LinkedList<E> implements List<E> {
    
    private int size;
    
    private Node head;
    
    private Node tail;
    
    public LinkedList() {
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.pre = head;
    }
    
    @Override
    public int size() {
        return size;
    }
    
    @Override
    public boolean isEmpty() {
        return size == 0;
    }
    
    @Override
    public void add(E e) {
        Node node = new Node(tail.pre, tail, e);
        tail.pre = node;
        node.pre.next = node;
        ++size;
    }
    
    @Override
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        Node node = findNode(index);
        return node.value;
    }
    
    @Override
    public E set(int index, E e) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        Node node = findNode(index);
        E oldVal = node.value;
        node.value = e;
        return oldVal;
    }
    
    private Node findNode(int index) {
        Node node;
        if (index < size / 2) {
            node = head.next;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
        } else {
            node = tail.pre;
            for (int i = size - 1; i > index; i--) {
                node = node.pre;
            }
        }
        return node;
    }
    
    @Override
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        Node node = findNode(index);
        E oldVal = node.value;
        node.pre.next = node.next;
        node.next.pre = node.pre;
        node.pre = null;
        node.next = null;
        size--;
        return oldVal;
    }
    
    @Override
    public void add(int index, E e) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }
        Node node = findNode(index);
        Node newNode = new Node(node.pre, node, e);
        newNode.pre.next = newNode;
        newNode.next.pre = newNode;
        ++size;
    }
    
    @Override
    public Iterator<E> iterator() {
        return new LinkedItr();
    }
    
    class LinkedItr implements Iterator<E> {
        
        Node cur = head;
        
        @Override
        public boolean hasNext() {
            return cur.next != tail;
        }
        
        @Override
        public E next() {
            if (cur.next == tail) {
                throw new NoSuchElementException();
            }
            cur = cur.next;
            return cur.value;
        }
    }
    
    class Node {
        Node pre, next;
        E value;
        
        public Node(Node pre, Node next, E value) {
            this.pre = pre;
            this.next = next;
            this.value = value;
        }
        
        public Node() {
        }
    }
}
